#include <iostream>
#include <vector>
#include <set>
#include "assert.h"

using namespace std;
string sortBasedOnFrequncy(string inputString)
{
	int len = inputString.length();
	if (len > INT_MAX)
	{
		return string("Invalid input! string is too long.");
	}
	//Step 1: initialize variables
	const int MAX = 256;
	int frequncyStore[MAX];
	int sortedIndicesStore[MAX];
	for (int i = 0 ; i < MAX ; ++i)
	{
		frequncyStore[i]=0;
		sortedIndicesStore[i]= i;
	}
	//Step 2: count occurrences
	const int length = inputString.size();
	for (int i = 0 ; i < length ; ++i)
	{
		++frequncyStore[inputString[i]];
	}
	//Step 3: convert 'zero' frequency to very big number for step 4
	for (int i = 0 ; i < MAX ; ++i)
	{
		frequncyStore[i] = frequncyStore[i] > 0 ? frequncyStore[i]: INT_MAX;
	}
	//Step 4: Sort sortedIndicesStore now based frequncyStore[sortedIndicesStore[i]]
	for (int i = 0 ; i < MAX ; ++i)
	{
		for (int j = 0 ; j < MAX ; ++j)
		{
			if(frequncyStore[sortedIndicesStore[j]] >  frequncyStore[sortedIndicesStore[i]])
			{
				int temp = sortedIndicesStore[j];
				sortedIndicesStore[j] = sortedIndicesStore[i];
				sortedIndicesStore[i] = temp;
			}
		}
	}
	//Step 5: construct the output
	string outputStr;
	for (int i = 0 ; i < MAX  && outputStr.length() < len ; ++i)
	{
		char currnetChar = sortedIndicesStore[i];
		string currentString;
		for (int j=0 ; j < frequncyStore[currnetChar] ; ++j )
		{
			currentString += currnetChar;
		}
		if (outputStr.length() + currentString.length() <= len)
		{
			outputStr += currentString;
		}
		else
		{
			return string("Error Occurred");
		}
	}
	return outputStr;
}

int main()
{
	//set<string> distinctSubStrs = generateDistinctSubStrings("KKKK");
	//set<string>::iterator itr= distinctSubStrs.begin();
	//for(;itr!=distinctSubStrs.end();itr++)
	//{
	//cout<<*itr<<endl;
	//}

	string sortedBasedOnFrequncy = sortBasedOnFrequncy("aaaabbbccd");
	return 0;
}